1. Field of Invention
The present invention relates to an apparatus, computer readable medium, transmission medium, and method for achieving bit timing synchronization of a received signal based on a maximum likelihood (ML) principle using a bisection technique. The invention is applicable to, for example, burst mode digital communication systems where data transmission is preceded by a preamble for acquisition of carrier and clock synchronization using the maximum likelihood principle.
2. Related Art
In burst mode digital communications, data transmissions are often preceded by a preamble consisting of L symbols to provide the rapid acquisition of both carrier and clock synchronization. Where the transmission utilizes M-ary PSK modulation, maximum likelihood symbol synchronization can be obtained by maximizing the following equivalent log-likelihood function F(xcfx84) based on the received signal samples during preamble period,
F(xcfx84)=[A(xcfx84)]2+[B(xcfx84)]2xe2x80x83xe2x80x83(1)
where A(xcfx84) and B(xcfx84) are given as                               A          ⁡                      (            τ            )                          =                              ∑                          n              =              0                                      L              -              1                                ⁢                      [                                                                                y                    R                                    ⁡                                      (                                          nT                      +                      τ                                        )                                                  ⁢                cos                ⁢                                  xe2x80x83                                ⁢                                  θ                  n                                            +                                                                    y                    I                                    ⁡                                      (                                          nT                      +                      τ                                        )                                                  ⁢                sin                ⁢                                  xe2x80x83                                ⁢                                  θ                  n                                                      ]                                              (        2        )                                          B          ⁡                      (            τ            )                          =                              ∑                          n              =              0                                      L              -              1                                ⁢                      [                                                            -                                                            y                      R                                        ⁡                                          (                                              nT                        +                        τ                                            )                                                                      ⁢                sin                ⁢                                  xe2x80x83                                ⁢                                  θ                  n                                            +                                                                    y                    I                                    ⁡                                      (                                          nT                      +                      τ                                        )                                                  ⁢                cos                ⁢                                  xe2x80x83                                ⁢                                  θ                  n                                                      ]                                              (        3        )            
In Eqs. 2 and 3, yR(nT+xcfx84) and yI(nT+xcfx84) are the received signal samples of the nth symbol, taken at instant nT+xcfx84 at the outputs of the matched filters in the in-phase and quadrature dimensions, respectively. xcex8n is the phase of nth symbol of the preamble, determined from the MPSK constellation.
The necessary conditions for the estimates of xcfx84 to be the maximum likelihood estimates requires that the partial derivative of likelihood function (1) with respect to the timing parameter be equal to zero:                               f          ⁡                      (                                          τ                ^                            ML                        )                          =                                            [                                                                    A                    ⁡                                          (                      τ                      )                                                        ⁢                                                            ∂                                              A                        ⁡                                                  (                          τ                          )                                                                                                            ∂                      τ                                                                      +                                                      B                    ⁡                                          (                      τ                      )                                                        ⁢                                                            ∂                                              B                        ⁡                                                  (                          τ                          )                                                                                                            ∂                      τ                                                                                  ]                                      τ              =                                                τ                  ^                                ML                                              =          0                                    (        4        )            
Therefore the maximization of likelihood function can be implemented by tracking the zeros of equation (4).
Conventionally, there are optimization schemes that can be used to maximize equation (1) or track the zeros for equation (4). One method used in synchronization is the steepest ascent method. Using the steepest ascent method, the iterative sequence is generated by: xcfx84k+1=xcfx84k+xcex1kƒ(xcfx84k). The iteration proceeds from an initial guess xcfx841 for the maximizing point to successive points: xcfx842, xcfx843, . . . , until some stopping condition is satisfied. This method has several disadvantages, however.
One of the primary disadvantages is that the rate of convergence can be relatively slow unless the initial approximation is sufficiently close to the solution. Further, the choice of step length xcex1k always results in a compromise between accuracy and efficiency, and finding the optimal step length is generally non-trivial and may increase computational complexity significantly. Finally this method is susceptible to noise. Noise and interference may result in divergence using the steepest ascent method.
The rate of convergence can be improved by using the Newton-Raphson method that makes use of the curvature information of the function. This method is a powerful and known numerical method of optimization. It involves generating the sequences {xcfx84n} defined by xcfx84k+1=xcfx84kxe2x88x92ƒ(xcfx84k)/ƒxe2x80x2(xcfx84k ). However, rapid convergence occurs only when the initial approximation is close to the actual root, and many problems can occur if the initial approximation is not sufficiently close to the actual root. The computational intensity of the Newton-Raphson method is significantly large because the derivative ƒxe2x80x2(xcfx84) (2nd derivative of likelihood function) needs to be evaluated in every iteration. Also, it is clear that the Newton-Raphson method can not be continued if ƒxe2x80x2(xcfx84k)≈0 for some k. These properties make the Newton-Raphson method less attractive in the implementation of the symbol synchronization.
It is an object of this invention to overcome the foregoing problems. In particular, it is an object of the invention to provide an apparatus, computer readable medium, transmission medium, and method for achieving symbol-timing synchronization of a received signal that are robust to noise, based on a maximum likelihood (ML) principle using a bisection technique.
It is a further object of the present invention to provide an apparatus, computer readable medium, transmission medium, and method for achieving symbol-timing synchronization of a received signal that will always converge to the optimal solution.
It is a yet a further object of the present invention to provide an apparatus, computer readable medium, transmission medium, and method for achieving symbol-timing synchronization of a received signal using a maximum likelihood (ML) principle and improving the linear convergence rate of bisection technique synchronization to second order by using the Aitken""s xcex942 method without adding much computational complexity.
These and other objects may be achieved in accordance with the present invention.
In the present invention, the preamble of the data transmission is sampled and the set of samples obtained is processed using optimization algorithms to provide the ML timing estimate.
In a first part of the invention, optimization algorithms are used in the isolation of the desired optimal estimate from non-optimal extremes satisfying the same necessary condition, and provide the initial conditions for activating the binary search schemes. Next, a binary search is conducted to obtain the optimal timing estimate. In another embodiment of the invention, a more rapidly convergent sequence can be constructed from bisection sequence to obtain the ML symbol timing. Using the obtained symbol timing estimate, the ML carrier phase estimate can be computed explicitly, and a synchronization can be conducted accordingly.